class Solution
{
public:
    int countLargestGroup(int n)
    {
        // n最大是10000, 各位之和最大是36(n=9999)
        int groupSizes[36] = {0};
        for (int i = 1; i <= n; ++i)
        {
            ++groupSizes[digitalSum(i) - 1];
        }
        int maxGroupSize = 0;
        int maxSizeGroupCount = 0;
        for (int groupSize : groupSizes)
        {
            if (groupSize > maxGroupSize)
            {
                maxGroupSize = groupSize;
                maxSizeGroupCount = 1;
            }
            else if (groupSize == maxGroupSize)
            {
                ++maxSizeGroupCount;
            }
        }
        return maxSizeGroupCount;
    }

private:
    int digitalSum(int n)
    {
        int sum = 0;
        while (n)
        {
            sum += n % 10;
            n /= 10;
        }
        return sum;
    }
};